package _02_linked_list.exerc.palindrome;

import _02_linked_list.exerc.ListNode;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 20:28
     * 判断是否是回文链表，正序和倒序的节点值一样
 */
public class MyTest {
    @Test
    public void test() {
        ListNode list = ListNode.of(new int[]{1, 2,3});
        ListNode list2 = ListNode.of(new int[]{1, 2, 1});
        ListNode list3 = ListNode.of(new int[]{1, 2, 2,1});
        ListNode list4 = ListNode.of(new int[]{1, 2, 3,3,2,1});
        System.out.println(isPalindrome(list));
        System.out.println(isPalindrome(list2));
        System.out.println(isPalindrome(list3));
        System.out.println(isPalindrome(list4));
    }

    /**
     * 步骤：
     *      1、找到中间节点
     *      2、从中间节点之后开始截取
     *      3、截取的链表与原链表逐一比较，有一个不一样没结束比较，返回 false
     * @param listNode
     * @return
     */
    boolean isPalindrome(ListNode listNode) {
        ListNode middle = findMiddle(listNode);
        ListNode newHead = reverse(middle);

        while (newHead != null) {
            if(newHead.val != listNode.val) {
                return false;
            }
            newHead = newHead.next;
            listNode = listNode.next;
        }
        return true;
    }

    /**
     * 查找链表中间节点
     * @param list
     * @return
     */
    ListNode findMiddle(ListNode list) {
        ListNode p1 = list;
        ListNode p2 = list;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    /**
     * 反转链表
     * @param list
     * @return
     */
    ListNode reverse(ListNode list) {
        if(list == null || list.next == null) {
            return list;
        }

        ListNode n1 = null;
        while (list != null) {
            ListNode o1 = list.next;
            list.next = n1;
            n1 = list;
            list = o1;
        }
        return n1;
    }
}
